package sample.xiaosong.greedyalgorithms;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 会议室问题
 *
 * 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
 * 给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，
 * 你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
 * 返回这个最多的宣讲场次。
 */
public class BestArrange {

    public static class Program {
        public int startTime;
        public int endTime;

        public Program(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }

    public static class ProgramComparator implements Comparator<Program> {
        @Override
        public int compare(Program o1, Program o2) {
            return o1.endTime - o2.endTime;
        }
    }

    /**
     * 贪心策略的切入点为：尽量早的结束会议，所以需要安装会议结束时间早的顺序排列
     *
     * 按结束时间排序好的队列，依次取出会议节点，大于等于开始时间即可开始会议
     * 结束一个会议之后，开始时间更新为该会议的结束时间
     * @param programs 所有会议列表
     * @param start 会议最早开始时间
     * @return 最多可以进行的会议场数
     */
    public static int getBestArrange(Program[] programs, int start) {
        if (programs == null || programs.length == 0) {
            return 0;
        }
        Arrays.sort(programs, new ProgramComparator());
        int result = 0;
        for (Program program : programs) {
            if (start <= program.startTime) {
                result++;
                start = program.endTime;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Program program1 = new Program(8, 9);
        Program program2 = new Program(8, 11);
        Program program3 = new Program(9, 11);
        Program program4 = new Program(9, 12);
        Program program5 = new Program(10, 11);
        Program program6 = new Program(11, 13);
        Program program7 = new Program(14, 15);
        Program program8 = new Program(16, 18);
        Program[] programs = new Program[]{program1, program2, program3, program4, program5, program6, program7, program8};
        System.out.println(getBestArrange(programs, 8));
    }
}
